/**
 * @author 挚爱之夕
 * @version 1.0
 * @implSpec 简单
 * 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
 * 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
 * 输入：n = 3
 * 输出：3
 * 解释：有三种方法可以爬到楼顶。
 * 1. 1 阶 + 1 阶 + 1 阶
 * 2. 1 阶 + 2 阶
 * 3. 2 阶 + 1 阶
 * @since 2023-09-06 16:49
 */
public class _070爬楼梯 {
    public static void main(String[] args) {
        int n = 3;
        System.out.println(new _070爬楼梯().climbStairs(n));
    }
    //动态规划 dp[i] = dp[i - 1] + dp[i - 2]
    public int climbStairs(int n) {
        int[] dp = new int[n + 1];
        //初始值
        dp[0] = 1;
        for(int i = 1; i < n + 1; i++){
            //从前一个楼梯过来
            dp[i] += dp[i - 1];
            //从前二个楼梯过来
            if(i >= 2) dp[i] += dp[i - 2];
        }
        return dp[n];
    }
    //优化空间
    public int climbStairs1(int n) {
        //只需要知道前两个楼梯的爬法数
        int[] dp = new int[2];
        dp[0] = 1;
        for(int i = 1; i < n + 1; i++){
            //上上个楼梯的爬法数就是dp[i%2]
            dp[i % 2] += dp[(i - 1) % 2];
        }
        return dp[n % 2];
    }
}
